Object-based application programs (written in Java, C++, or the like) usually operate on directed graphs. These graphs comprise root objects and regular objects which are interconnected by means of pointers. During the execution of an object-based application program the graph dynamically changes as objects and/or pointers are added, modified or removed.
Object-based execution environments often support the application developer in one of the most tedious and error-prone tasks in programming, namely memory handling. In many systems, objects are only allocated by the application program, but never explicitly de-allocated. In these systems it is the task of a so-called garbage collector (GC) to determine which objects are no longer needed. Furthermore, the GC frees-up the respective memory and returns it to the heap of unused memory. A GC must, every once in a while, clean up wasted memory. In addition, the GC might be used to compact memory by eliminating the gaps created by fragmentation.
Cleaning up the garbage in memory is usually done in two steps, referred to as marking and sweeping. The current SUN Java garbage collector also uses the mark-and-sweep approach according to which every root object in the system is marked initially. Then one follows all the object references inside those objects to other objects not yet marked, and so on, recursively. Finally, when there are no more references to follow, all the unmarked objects are deleted.
Current GC schemes are not well suited for use in resource constrained systems because these GC schemes require more volatile memory which than usually available in these kind of systems.
An integrated circuit card (ICC), more widely known as smartcard, is one example of such a resource constrained system. Other examples are: mobile and/or hand held devices, such as cellular phones, pagers, personal digital assistants, personal area network devices, and so forth.
In the following, we will focus mainly on ICCs and smartcards in particular. The smartcard concept began in Europe prior to 1985, and is today being used in telephone systems, toll roads, game parlors, and personal computers, just to mention some applications.
In the following, the term integrated circuit card will be used, because ISO uses the term to encompass all those devices where an integrated circuit is contained within a card-size piece of plastic, or the like.
Typical ICCs comprise a microprocessor (central processing unit, CPU), a read-only memory (ROM), a volatile random-access memory (RAM), and some type of non-volatile, programmable memory, such as an EEPROM (electrically erasable programmable read only memory). In addition, an ICC usually comprises some kind of a bus (such as a serial bus) and I/O ports for interconnection to a card terminal.
The contents of the ROM type of memory is fixed and can not be changed once manufactured by the semiconductor company. This is a low cost memory, in that it occupies minimum space on the substrate. It is a disadvantage of a ROM that it cannot be changed and that it takes several months to be produced. As opposed to this, an EEPROM is erasable by the user and can be rewritten many times. ROMs and EEPROMs are non volatile. In other words, when the power is removed they still retain their contents.
A RAM is a volatile memory and as soon as the power is removed the data content is lost. A RAM, however, has the advantage that it is much faster than ROMs and EEPROMs. On the other hand, a RAM is more expensive in terms of die size. Usually, the RAM is relatively small. RAM is not used at all for any type of operation involving data that has to be kept permanent and consistent. Unfortunately, always using non-volatile memory has a couple of serious drawbacks. One is the extreme performance penalty that has to be paid as every memory write access is roughly 500 to thousand times slower when using EEPROM instead of RAM. An even more serious problem is the limitation on the amount of guaranteed write cycles (100000 times for EEPROM).
It is an object of the present invention to provide a novel garbage identification and garbage collection scheme, and in particular garbage identification and garbage collection scheme which is well suited for use in resource constrained systems.
It is an object of the present invention to provide a solution for garbage collection in resource constrained systems, such as an integrated circuit cards.